package com.yanceysong.codetop.s81_s90;

public class S81_Mid_162_寻找峰值 {
    /**
     * .S81_Mid_162_寻找峰值
     * .<p>
     * .LeetCode链接: <a href="https://leetcode.cn/problems/find-peak-element/">...</a>
     * .<p>
     * .【题目描述】
     * .峰值元素是指其值严格大于左右相邻值的元素。给定一个整数数组 nums，找到一个峰值元素并返回其索引。
     * .数组可能包含多个峰值，返回其中 任意 一个即可。你可以假设 nums[-1] = nums[n] = -∞，这使得边界元素也可能成为峰值。
     * .要求时间复杂度 O(log n)。
     * .<p>
     * .【核心标签】二分查找 / 数组 / 思维
     * .<p>
     * .【示例】
     * .示例1: 输入 nums = [1,2,3,1] 输出: 2 解释: 索引2的元素3是峰值
     * .示例2: 输入 nums = [1,2,1,3,5,6,4] 输出: 5 或 1 解释: 索引5的元素6是峰值；索引1的元素2也是峰值
     * .<p>
     * .【关键性质】
     * .1. 相邻元素不相等 (题目原始条件: nums[i] != nums[i+1])，这保证了严格比较有效；若输入偶尔不满足该条件，本算法仍会返回一个“局部 >=”点。
     * .2. 将数组视为一系列“上坡-下坡”的片段，必然存在峰值。
     * .3. 如果 nums[mid] > nums[mid + 1]，说明右侧在 mid+1 处开始走“下坡”，峰值一定在左半部分（含 mid）。否则说明仍在“上坡”，峰值在右半部分（不含 mid）。
     * .<p>
     * .【二分查找思想】
     * .通过比较 mid 与 mid+1 来判断当前所处的坡的走势，逐步收缩区间直到 left == right，即找到一个峰值位置。
     * .不需要显式比较 mid 与 mid-1，因为比较 mid 与 mid+1 已经决定了去向且不会漏峰。
     * .<p>
     * .【复杂度】时间 O(log n)，空间 O(1)。
     * .<p>
     * .【ASCII 图解】
     * .例：数组 [1, 2, 1, 3, 5, 6, 4]
     * .正常俯视值曲线（纵向展示）：
     * .index:   0  1  2  3  4  5  6
     * .value:   1  2  1  3  5  6  4
     * .            ↑           ↑
     * .            峰          峰
     * <p>
     * .将数值“旋转45°”的概念化（斜对角升降的可视化，仅用于辅助理解上坡/下坡趋势）：
     * .把每个元素沿右上方向递增绘制，上坡连续升高，遇到下降说明经过峰值：
     * <p>
     * .                      (6)
     * .                  (5)    (4)
     * .       (2)    (3)
     * .   (1)    (1)
     * .斜视角示意：当你在比较 mid 与 mid+1，其实是在判断当前斜坡是否继续向右上攀升；若不再攀升（出现下降），峰值在左边。
     * .注：这是把一维数组用对角排布展示，使得“上升”像继续向右上延伸，“下降”则折回到下方，便于心理模型建立。
     * <p>
     * .【搜索过程演示】以 [1,2,3,1] 为例：
     * .初始: left=0, right=3
     * .mid=1 (nums[1]=2, nums[2]=3) -> 2 < 3 仍在上坡 => left=mid+1=2
     * .区间 [2,3] mid=2 (nums[2]=3, nums[3]=1) -> 3 > 1 出现下坡 => right=mid=2
     * .left == right == 2，结束，返回 2
     * <p>
     * .【关键洞察】
     * .1. 与经典“找局部峰值”问题的线性扫描不同，这里利用单调趋势判断直接二分。
     * .2. 不必显式处理边界为 -∞，比较逻辑天然兼容：当 mid 在右半段上坡中，继续靠右；否则靠左包含 mid。
     * .3. 收缩规则保证不会遗漏：下降拐点时把 mid 包含进来，以免正好就是峰值。
     * <p>
     * .【正确性要点校验】
     * .若 nums[mid] > nums[mid+1]：右侧呈下降，峰值在 [left, mid]。若 mid 自身是峰值（前面可能上升或边界），保留它。
     * .若 nums[mid] < nums[mid+1]：右侧仍有上升潜力，峰值一定在 (mid, right]，舍弃 mid。
     * .循环终止时，left == right，指向某个峰值索引。
     */
    public int findPeakElement(int[] nums) {
        int left = 0;              // 搜索区间左边界
        int right = nums.length - 1; // 搜索区间右边界
        // 循环不变量：峰值一定在 [left, right]
        while (left < right) {
            // 取中点（避免溢出的写法：left + (right - left)/2，数据规模安全可用 >> 1）
            int midIndex = left + (right - left)/2;

            // 对比当前 mid 与其右侧元素，判断走势
            if (nums[midIndex] > nums[midIndex + 1]) {
                // 出现下降：峰值在左区间（含 midIndex）
                right = midIndex;
            } else {
                // 仍在上升：峰值在右区间（不含 midIndex）
                left = midIndex + 1;
            }
        }
        // left == right 指向某个峰值
        return left;
    }

    // =============== 辅助校验方法 ===============

    /**
     * .校验某索引是否为峰值（用于测试断言）
     */
    private static boolean isPeak(int[] nums, int idx) {
        int n = nums.length;
        int leftVal = (idx - 1 >= 0) ? nums[idx - 1] : Integer.MIN_VALUE; // 视作 -∞
        int rightVal = (idx + 1 < n) ? nums[idx + 1] : Integer.MIN_VALUE; // 视作 -∞
        return nums[idx] > leftVal && nums[idx] > rightVal;
    }

    /**
     * .打印数组及峰值位置，并用简单“山峰”ASCII展示（竖向）
     */
    private static void printArrayWithPeak(int[] nums, int peakIdx) {
        System.out.print("数组: [");
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i]);
            if (i < nums.length - 1) System.out.print(", ");
        }
        System.out.println("]  峰值索引=" + peakIdx + " 值=" + nums[peakIdx]);

        // 竖向山峰（值最大在顶部）
        int max = nums[peakIdx];
        System.out.println("竖向山峰示意 (值越大位置越高)：");
        for (int level = max; level >= 1; level--) {
            StringBuilder sb = new StringBuilder();
            for (int v : nums) {
                sb.append(v >= level ? " * ." : "   ");
            }
            System.out.println(sb);
        }
        // 标记索引行
        StringBuilder idxRow = new StringBuilder();
        for (int i = 0; i < nums.length; i++) {
            idxRow.append(String.format("%2d ", i));
        }
        System.out.println(idxRow);

        // 45° 斜视角（对角线排布）
        System.out.println("45°旋转斜视角（对角线排布，仅概念化展示上升/下降趋势）：");
        // 通过在前面加入空格递增模拟右上扩展
        for (int i = 0; i < nums.length; i++) {
            StringBuilder line = new StringBuilder();
            // 控制缩进使其斜向排列
            for (int s = 0; s < i; s++) line.append("  ");
            line.append(String.format("(%d)", nums[i]));
            if (i == peakIdx) line.append(" <- 峰");
            System.out.println(line);
        }
        System.out.println();
    }

    public static void main(String[] args) {
        S81_Mid_162_寻找峰值 solver = new S81_Mid_162_寻找峰值();
        System.out.println("=== 寻找峰值测试开始 ===\n");

        // 测试1: 示例1
        int[] case1 = {1, 2, 3, 1};
        int p1 = solver.findPeakElement(case1);
        assert isPeak(case1, p1) : "案例1失败";
        System.out.println("案例1 [1,2,3,1] -> 峰值索引=" + p1);
        printArrayWithPeak(case1, p1);

        // 测试2: 示例2
        int[] case2 = {1, 2, 1, 3, 5, 6, 4};
        int p2 = solver.findPeakElement(case2);
        assert isPeak(case2, p2) : "案例2失败";
        System.out.println("案例2 [1,2,1,3,5,6,4] -> 峰值索引=" + p2);
        printArrayWithPeak(case2, p2);

        // 测试3: 单元素
        int[] case3 = {42};
        int p3 = solver.findPeakElement(case3);
        assert isPeak(case3, p3) : "案例3失败";
        System.out.println("案例3 [42] -> 峰值索引=" + p3);
        printArrayWithPeak(case3, p3);

        // 测试4: 严格递增（最后一个为峰）
        int[] case4 = {1, 2, 3, 4, 5, 6};
        int p4 = solver.findPeakElement(case4);
        assert isPeak(case4, p4) : "案例4失败";
        System.out.println("案例4 递增 -> 峰值索引=" + p4);
        printArrayWithPeak(case4, p4);

        // 测试5: 严格递减（第一个为峰）
        int[] case5 = {9, 7, 5, 3, 1};
        int p5 = solver.findPeakElement(case5);
        assert isPeak(case5, p5) : "案例5失败";
        System.out.println("案例5 递减 -> 峰值索引=" + p5);
        printArrayWithPeak(case5, p5);

        // 测试6: 多峰值随机数组
        int[] case6 = {3, 5, 4, 6, 2, 7, 1, 8, 3};
        int p6 = solver.findPeakElement(case6);
        assert isPeak(case6, p6) : "案例6失败";
        System.out.println("案例6 多峰 -> 峰值索引=" + p6);
        printArrayWithPeak(case6, p6);

        // 测试7: 边界峰值（峰在索引0）
        int[] case7 = {10, 5, 4, 3};
        int p7 = solver.findPeakElement(case7);
        assert isPeak(case7, p7) : "案例7失败";
        System.out.println("案例7 边界左侧峰 -> 峰值索引=" + p7);
        printArrayWithPeak(case7, p7);

        // 测试8: 边界峰值（峰在最后索引）
        int[] case8 = {2, 4, 6, 9};
        int p8 = solver.findPeakElement(case8);
        assert isPeak(case8, p8) : "案例8失败";
        System.out.println("案例8 边界右侧峰 -> 峰值索引=" + p8);
        printArrayWithPeak(case8, p8);

        // 测试9: 模拟大数组（简化，不打印图形）
        int n = 1000;
        int[] case9 = new int[n];
        for (int i = 0; i < n; i++) case9[i] = i; // 严格递增，峰在末尾
        int p9 = solver.findPeakElement(case9);
        assert isPeak(case9, p9) : "案例9失败";
        System.out.println("案例9 大数组（递增） -> 峰值索引=" + p9 + " (期望:" + (n - 1) + ")");

        // 测试10: 人工构造峰在中间
        int[] case10 = {1, 3, 5, 7, 6, 4, 2};
        int p10 = solver.findPeakElement(case10);
        assert isPeak(case10, p10) : "案例10失败";
        System.out.println("案例10 中央峰 -> 峰值索引=" + p10);
        printArrayWithPeak(case10, p10);

        System.out.println("=== 所有测试完成，算法验证通过 ===");
    }
}
